
#include <cstdlib>   
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <cassert>
#include <bits/stl_map.h>
#include <bits/stl_vector.h>

typedef unsigned int uint;

using namespace std;

class Stream;
class Event;

typedef map<uint,map<uint,set<Stream*>*>*> PMap;

string 
TT(uint n) 
{
    stringstream    ss;
    ss << " ";
    if (n < 100) {
        ss << " ";
    }
    if (n < 10) {
        ss << " ";
    }
    ss << n;
    return ss.str();
}

uint    nsPerBit = 0;

class Stream {
public:
            Stream(const string &n, uint s, uint p) : name_(n), size_(s), duration_(0), period_(p), normal_(0), offset_(0) {}
    string  name_;
    uint    size_;
    uint    duration_;
    uint    period_;
    uint    normal_;
    uint    offset_;
};

class Event {
public:
            Event(Stream *s, uint att) : stream_(s), pred_(NULL), stt_(0), att_(att) {}
    Stream  *stream_;
    Event   *pred_;
    uint    stt_;
    uint    att_;
};

uint
readLines(const string &fn, vector<string> &v)
{
    v.clear();
    ifstream    infile;
    infile.open(fn.c_str());
    if(infile) {
        string  s;
        while(getline(infile, s)) {
            v.push_back(s);
        }
    }
    return v.size();
}

uint
readStreams(const vector<string> &v, PMap &pMap)
{
    string  first(v[0]);
    stringstream ss(first);
    double  rate;
    if (!(ss >> rate)) {
        cout << "Error" << endl;
        exit(1);
    }
    nsPerBit    = 1000/rate;
    
    vector<Stream*> vs;
    uint    high = 0;
    uint    low = uint(-1);
    for (uint i = 1; i < v.size(); i++) {
        string  t(v[i]);
        string  name;
        uint    size, period;
        stringstream    ss(t);
        if (!(ss >> size >> name >> period)) {
            continue;
        }
        high    = max(period, high);
        low     = min(period, low);
        Stream  *s = new Stream(name, size, period);
        vs.push_back(s);
    }
    for (uint n = 0; n < vs.size(); n++) {
        Stream  *s = vs[n];
        uint    period  = s->period_;
        uint    normal  = period/low;
        s->duration_    = ((s->size_ + 60) * 8 * nsPerBit)/1000;
        s->normal_      = normal;
        map<uint,set<Stream*>*> *sMap = pMap[normal];
        if (sMap == NULL) {
            sMap = new map<uint,set<Stream*>*>();
            pMap[normal] = sMap;
        }
        set<Stream*>    *z = (*sMap)[s->size_];
        if (z == NULL) {
            z = new set<Stream*>();
            (*sMap)[s->size_] = z;
        }
        z->insert(s);
    }   
    return high;
}

void
listStreamsForSize(set<Stream*> *z, vector<Stream*> &v)
{
    set<Stream*>::iterator tit = z->begin();
    for (; tit != z->end(); tit++) {
        Stream *s = *tit;
        assert(s);
        v.push_back(s);
    }
}

void
listStreamsForPeriod(map<uint,set<Stream*>*> *m, vector<Stream*> &v)
{
    if (m == NULL) {
        v.push_back(NULL);
        return;
    }
    map<uint, set<Stream*>*>::reverse_iterator sit = m->rbegin();
    for (; sit != m->rend(); sit++) {
        vector<Stream*> vv;
        listStreamsForSize(sit->second, vv);
        v.insert(v.end(), vv.begin(), vv.end());
    }
}

void
listStreams(PMap &m, vector<Stream*> &v)
{
    map<uint,map<uint,set<Stream*>*>*>::iterator pit = m.begin();
    for (; pit != m.end(); pit++) {
        vector<Stream*> vv;
        listStreamsForPeriod(pit->second, vv);
        v.insert(v.end(), vv.begin(), vv.end());
    }
}

void
schedule(PMap &pMap, uint maxPeriod)
{
    vector<vector<uint>*>   at;    
    vector<vector<Event*>*> av;
    uint    len     = 0;
    uint    skip    = 0;
    uint    p       = pMap.begin()->first;
    uint    last    = pMap.rbegin()->first;
    while (p <= last) {
        uint repeat = last / p;
        len = max(len, repeat);
        
        vector<Stream*> v;
        listStreamsForPeriod(pMap[p], v);

        bool    even = true;
        for (uint n = 0; n < v.size(); n++) {

            uint            i = 0;
            vector<Event*>  &ve = *new vector<Event*>(len);
            av.push_back(&ve);
            vector<uint>    &vt = *new vector<uint>(1);
            vt[0] = 0;
            at.push_back(&vt);

            if (!even) {
                i += (skip+1)/2;
            }

            Stream  *s = v[n];
            uint    att = 0;
            Event   *pred = NULL;
            for (uint j = 0; j < repeat; j++) {
                
                Event *e = new Event(s, att);
                e->pred_ = pred;
                pred = e;
                
                if (s) {
                    att += s->period_;
                }
                
                ve[i] = e;
                i += skip;
                i++;
            }
            even = !even;
        }
        p *= 2;
        skip = ((skip + 1) * 2) - 1;
    }

    uint    rows = av.size();
    uint    cols = av[0]->size();

    for (uint a = 0; a < rows; a++) {
        for (uint j = 0; j < cols; j++) {
            Event *e = (*av[rows - a - 1])[j];
            if (e) {
                if (e->stream_) {
                    cout << TT(e->stream_->period_);
                    continue;
                }
            }
            cout << "   .";
        }
        cout << endl;
    }

    cout << endl;

    set<Stream*>        offsetOk;
    uint                t = 0;
    vector<Event*>      sched;
    map<Stream*,uint>   offset;
    for (uint c = 0; c < cols; c++) {
        for (uint r = 0; r < rows; r++) {
            Event *e = (*av[rows - r - 1])[c];
            if (e) {
                sched.push_back(e);
                
                Stream  *s = e->stream_;
                if (s == NULL) {
                    continue;
                }
                
                if (offsetOk.count(s) == 0) {
                    s->offset_ = t;
                    offsetOk.insert(s);
                }
                e->att_ += s->offset_;
                
                if (t < e->att_) {
                    t = e->att_;
                }
                
                if (t > e->att_) {
                    cout << "*** ERROR *** Unfeasible schedule" << endl;
                }

                cout << TT(t) << " " << TT(e->att_) << " " << TT(s->period_) << " " << s->name_ << " " << TT(s->duration_) << endl;
                
                t += s->duration_;
            }
        }
    }    
    cout << endl ;
    
    for (uint i = 0; i < sched.size(); i++) {
        Event   *e = sched[i];
        Stream  *s = e->stream_;
    }
}

void
dumpStreams(PMap pMap)
{
    vector<Stream*> v;
    listStreams(pMap, v);
    for (uint i = 0; i < v.size(); i++) {
        Stream  *s = v[i];
        cout << s->name_ << " p:" << s->period_ << " n:" << s->normal_ << endl;
    }
    cout << endl;
}

int 
main(int argc, char** argv) 
{
    PMap    pMap;
    
    string  fn(argv[1]);
    vector<string>  lines;

    uint    nLines      = readLines(fn, lines);
    uint    maxPeriod   = readStreams(lines, pMap);

    dumpStreams(pMap);
    
    schedule(pMap, maxPeriod);
    
    cout << endl << maxPeriod << endl;
    return 0;
}

